package com.tgy.cmp;

import com.tgy.Sort;

/**
 * @Author: tgy
 * @Date: 2020-10-14 09:20
 */
public class InsertionSort<E> extends Sort<E> {


    @Override
    protected void sort() {

        int location;
        E last;
        for (int i = 1; i < elements.length; i++) {

            // logn
            location = indexOfElement(i);
            last = elements[i];

            if (location == i) {
                continue;
            }

            // n
            for (int j = i; j > location; j--) {

                elements[j] = elements[j - 1];
            }

            elements[location] = last;
        }

    }


    private void normalSort() {

        E lastE;
        for (int i = 1; i < elements.length; i++) {

            lastE = elements[i];
            int j = i - 1;
            for (; j >= 0; j--) {

                // 这里不能使用 <= ,会导致排序变成不稳定
                if (compare(lastE,elements[j]) < 0) {

                    elements[j+1] = elements[j];
                }else {

                    break;
                }
            }

            if ((j + 1) != i) {

                elements[j + 1] = lastE;
            }
        }
    }
    private int indexOfElement(int index) {

        int start = 0, end = index, mid = 0;
        int result = 0;
        while (start < end) {

            mid = (start + end) >> 1;

            result = compare(index, mid);
            if (result < 0) {

                // index 小于 mid ，往 左
                end = mid;
            }else {

                // 大于或者等于 mid ,往 右
                start = mid + 1;
            }
        }

        return start;
    }

    private int indexOfElement01(int index) {

        int start = 0, end = index, mid = 0;
        int result = 0;
        while (start < end) {

            mid = (start + end) >> 1;

            result = compare(index, mid);
            if (result < 0) {

                end = mid;
            }else if (result > 0) {

                start = mid + 1;
            }else {

                break;
            }
        }

        if (result == 0) {

            for (int i = mid + 1; i < index; i++) {

                if (compare(index,i) < 0) {

                    return i;
                }
            }

            return index;

        }else if (result < 0) {

            return mid;
        }else {

            return mid + 1;
        }
    }

    /**
     * 二分查找
     * @param nums
     * @return
     */
    public int binarySearch(Integer[] nums, Integer element) {

        if (nums.length == 0) {

            return -1;
        }

        // 这里 end取值 length， 每个区间都是 [a,b)
        int start = 0, end = nums.length, mid;
        while (start < end) {

            mid = (start + end) >> 1;

            if (nums[mid] < element) {

                start = mid + 1;
            }else if (nums[mid] > element) {

                end = mid;
            }else {

                return mid;
            }
        }

        return -1;
    }
}
